package com.lw.leetcode.node;

/**
 * 124. 二叉树中的最大路径和
 *
 * @Author liw
 * @Date 2021/5/6 16:39
 * @Version 1.0
 */
public class MaxPathSum {

    long sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        find(root);
        return (int) sum;
    }

    private long find(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        long l = find(root.left);
        long r = find(root.right);
        sum = Math.max(Math.max(sum, l + r + root.val), Math.max(root.val, Math.max(r + root.val, l + root.val)));
        return Math.max(root.val, root.val + Math.max(r, l));
    }

}
